package com.kehao.leetcode.algorithm;

import org.junit.Test;

import java.util.Arrays;

//https://leetcode-cn.com/problems/partition-equal-subset-sum/
public class Solution416 {

    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).reduce(0, (a, b) -> a + b);
        if(sum%2==1){
            return false;
        }
        int half = sum/2;
        boolean[][] dp = new boolean[nums.length][half+1];//dp[i][j] 前i+1个元素能否凑到数目j

        for (int i = 0; i < half+1; i++) {
            dp[0][i] = nums[0]==i? true : false;
        }
        for (int i = 0; i < nums.length; i++) {
            dp[i][0] = true;

        }

        for (int i = 1; i < nums.length; i++) {
            for (int j = 1; j < half+1; j++) {
                if(j-nums[i]>=0){
                    dp[i][j] = dp[i-1][j] ||dp[i-1][j-nums[i]];
                }else {
                    dp[i][j] = dp[i-1][j] ;
                }
            }
        }

//        for (int i = 0; i < nums.length; i++) {
//            for (int j = 0; j < half; j++) {
//                System.out.print(dp[i][j]+"   ");
//            }
//            System.out.println();
//        }

        return dp[nums.length-1][half];
    }

    @Test
    public void myTest01(){
        System.out.println(canPartition(new int[]{1, 5, 11, 5}));
    }

    @Test
    public void myTest02(){
        System.out.println(canPartition(new int[]{1, 2, 3, 5}));
    }

    @Test
    public void myTest03(){
        System.out.println(canPartition(new int[]{1,5,3}));
    }

    @Test
    public void myTest04(){
        System.out.println(canPartition(new int[]{1,1}));
    }

    @Test
    public void myTest05(){
        System.out.println(canPartition(new int[]{1,1,1,1}));
    }

}
